package dataStructure.hashTable_;

import java.util.LinkedList;

/**
 * @author lhn
 * @date 2024-09-02 16:26
 */

public class HashTable_ {

    public static void main(String[] args) {
        HashTab hashTab = new HashTab(2);
        hashTab.add(new Employee(1, "qwer"));
        hashTab.add(new Employee(2, "asdf"));
        hashTab.add(new Employee(3, "zxcv"));
        hashTab.add(new Employee(4, "uiop"));
        hashTab.list();
        System.out.println(
                hashTab.query(3)
        );
        System.out.println(
                hashTab.query(15)
        );
        hashTab.delete(4);
        hashTab.list();
    }

}
//表示哈希表，管理链表
class HashTab{
    private EmployeeLinkedList[] employeeLinkedListArray;
    private int size;

    public HashTab(int size) {
        this.size = size;
        employeeLinkedListArray = new EmployeeLinkedList[size];
        //初始化链表

        for (int i = 0; i < employeeLinkedListArray.length; i++) {
            employeeLinkedListArray[i] = new EmployeeLinkedList();
        }
    }
    //编写散列函数
    public int hashFun(int id){
        return id % this.size;
    }

    //添加员工
    public void add(Employee employee){
        //根据id确定添加到哪个链表
        int id = employee.getId();
        int index = hashFun(id);
        employeeLinkedListArray[index].add(employee);
    }

    public void list() {
        for (int i = 0; i < size; i++) {
            System.out.println("第 " + (i + 1) + " 链表");
            employeeLinkedListArray[i].print();
        }
    }

    public Employee query(int id){
        int index = hashFun(id);
        EmployeeLinkedList employeeLinkedList = employeeLinkedListArray[index];
        if (employeeLinkedList.isEmpty()) {
            System.out.print("链表为空");
            return null;
        } else {
            Employee employee = employeeLinkedList.query(id);
            if (employee==null) {
                System.out.print("id为 " + id + " 的用户没有找到 ");
                return null;
            } else {
                System.out.print("id为 " + id + " 的用户已找到 ");
                return employee;
            }
        }

    }

    public void delete(int id){
        int index = hashFun(id);
        if (employeeLinkedListArray[index].isEmpty()) {
            System.out.print("链表为空");
            return;
        } else {
            employeeLinkedListArray[index].delete(id);
        }
    }
}

//表示链表
class EmployeeLinkedList{
    //头指针，执行第一个节点，这个节点是直接指向第一个雇员的
    private Employee head; //默认null
    //添加雇员到链表
    //说明
    //1. 假定，当添加雇员时，id是自增的，即id的分配总是从小到大
    //2. 因此，直接将雇员，按其id值，添加到链表最后
    public void add(Employee employee){
        //如果是第一个节点，那么直接添加
        if(head == null){
            head = employee;
            return;
        }
        //如果不是第一个节点，那么需要辅助指针完成添加
        Employee temp = head;
        while (temp != null){
            if(temp.getNext() == null){
                break;
            }
            temp = temp.getNext();
        }
        temp.setNext(employee);
    }

    public void print(){
        if (head == null) {
            System.out.println("链表为空");
            return;
        }
        Employee temp = head;
        System.out.println(" id     " + "   name ");
        while (temp != null){
            System.out.println(" " + temp.getId() + "       " + temp.getName());
            temp = temp.getNext();
        }
    }

    public Employee query(int id){
        Employee temp = head;
        while (temp != null){
            if (temp.getId() == id) {
                return temp;
            }
            temp = temp.getNext();
        }
        return null;
    }

    public void delete(int id){
        if (head == null) {
            System.out.println("链表为空，无法删除");
            return;
        }
        //如果头节点就是我们要找的，直接删除
        if (head.getId() == id) {
            head = head.getNext();
            return;
        }
        Employee temp = head;
        while (temp != null){
            if (temp.getNext().getId() == id) {
                temp.setNext(temp.getNext().getNext());
                return;
            }
            temp = temp.getNext();
        }
    }

    public boolean isEmpty(){
        Employee temp = head;
        while (temp == null){
            return true;
        }
        return false;
    }
}

//表示一个雇员
class Employee{
    private int id;
    private String name;
    private Employee next;

    public Employee(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Employee getNext() {
        return next;
    }

    public void setNext(Employee next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Employee{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}